/*
Date:20210422 22:17pm
key:每层都建立一个柱状图模型，注意柱状图模型的建立，这里要三个循环，遍历每层，遍历每列，每列从最底层往上走累加。由下往上碰到0则断
    柱状图那里是一个单调递增栈，碰到小的就开始弹出算面积，直到小的能放入。
*/vecttor全部置为0不要通过auto j:v
class Solution {
public:
void clean(vector<int>&v)
{
           for(int i=0;i<v.size();i++)
            {
                v[i]=0;
            }
}
int Square(vector<int>&heights)
{
            if(heights.size()==0)
        {
            return 0;
        }
        //如果一开始就单调递减，那些后面的元素就不知道可以从头开始，因为栈里面它们底下没有东西，因此一开始压入0，保证最底下一直有东西。还有就是注意下标是怎么减出宽度的。
        heights.insert(heights.begin(),0);
        //最后的哨兵0是让它原末尾能停止
        heights.push_back(0);
        stack<int>S;
        S.push(0);
        int Max=0;
        int square;
        for(int i=1;i<heights.size();i++)
        {
            if(heights[S.top()]<=heights[i])
            {
                S.push(i);
            }
            else
            {
                while(!S.empty()&&heights[S.top()]>heights[i])
                {
                    //更新
                    int now=S.top();
                    S.pop();
                    square=heights[now]*(i-S.top()-1);
                    if(square>Max)
                    {
                        Max=square;
                    }

                    
                }
                S.push(i);
            }
        }
        return Max;
}
    int maximalRectangle(vector<vector<char>>& matrix) 
    {
        if(matrix.size()==0){return 0;}
        
        vector<int>v;
        v.resize(matrix[0].size());
        int max=0;
        for(int i=0;i<matrix.size();i++)
        {
            clean(v);
            for(int j=0;j<matrix[0].size();j++)
            {
                for(int k=i;k>=0;k--)
                {
                    int g=matrix[k][j]-48;
                    if(g==0){break;}//由下往上碰到0马上断
                    v[j]+=g;
                }
                //cout<<v[j]<<' ';
            }

            if(Square(v)>max)
            {
                max=Square(v);
            };
        }
        return max;
    }
};